#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *给你一个非负整数数组 nums ，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

 

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/jump-game-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
//每次选择最大的
int jump12(vector<int>& nums) {
    if (nums.size() == 1) return 0;
    int curDistance = 0; // 当前覆盖最远距离下标
    int ans = 0; // 记录⾛的最⼤步数
    int nextDistance = 0; // 下⼀步覆盖最远距离下标
    for (int i = 0; i < nums.size(); i++) {
        nextDistance = max(nums[i] + i, nextDistance); // 更新下⼀步覆盖最远距离下标
        if (i == curDistance) { // 遇到当前覆盖最远距离下标
            if (curDistance != nums.size() - 1) { // 如果当前覆盖最远距离下标不是

                ans++; // 需要⾛下⼀步
                curDistance = nextDistance; // 更新当前覆盖最远距离下标（相

                if (nextDistance >= nums.size() - 1) break; // 下⼀步的覆盖范围已经可以

            } else break; // 当前覆盖最远距离下标是集合终

        }
    }
    return ans;
}



int jump22(vector<int>& nums) {
    if (nums.size() == 1) return 0;
    int count=0;
    int maxIndex=0;//指向的最大下标
    int maxIndexNext=0;//指向下一个最大坐标
    for (int i = 0; i <nums.size() ; ++i) {
        maxIndexNext= max(maxIndexNext,nums[i]+i);
        if (maxIndexNext>=nums.size()-1)
            return count+1;//直接返回+1 加上当前步骤

        if (i==maxIndex){
            count++;
            maxIndex=maxIndexNext;
        }

    }
    return count;

}


//尝试DP方式解决 todo 我草这个我似乎没看
int jum2323p(vector<int>& nums) {

    const int size = nums.size();
    int dp[size];
    dp[0] = 0;

    for(int i = 1; i < size; i++)
        dp[i] = INT32_MAX;

    for(int i = 0; i < nums.size(); i++){
        int step = nums[i];
        for(int j = 1; j <= step && j + i < nums.size(); j++){
            dp[j + i] = min(dp[j + i], dp[i] + 1);
        }
    }


    for (int i = 0; i <size; ++i) {
        cout<<dp[i]<<" ";
    }

    return dp[size - 1];
}



//public int jump(int[] nums) {
//    int []dp = new int[nums.length];
//    dp[0] = 0;
//    int min = Integer.MAX_VALUE;
//    for (int i = 0; i < dp.length - 1; i++){
//        for (int j = i + 1; j <= nums[i] + i && j < dp.length; j++) {
//            if (dp[j] != 0)
//                dp[j] = Math.min(dp[i] + 1, dp[j]);
//            else
//                dp[j] = dp[i] + 1;
//        }
//    }
//    return dp[dp.length - 1];
//}